#include <iostream>
#include <vector>
#include <algorithm> // 用于sort
using namespace std;

// 表示需求区间的结构体
struct RequestRange {
    int left, right; // 左右边界

    RequestRange(int l, int r) : left(l), right(r) {}
};

// 自定义比较函数
bool my_compare(const RequestRange& a, const RequestRange& b) {
    if (a.left != b.left) return a.left < b.left;
    return a.right < b.right;
}

// 使用排序+贪心求最小建设基站数量
int minStations(const vector<vector<int>>& ranges) {
    // 边界判断：一个需求都没有那就返回0
    if (ranges.empty()) return 0;

    // 将输入转换成对象数组，然后排序
    vector<RequestRange> arr;
    for (const auto& range : ranges) {
        arr.emplace_back(range[0], range[1]);
    }
    sort(arr.begin(), arr.end(), my_compare);

    // 每一座基站在尽可能多覆盖需求的前提下尽可能放右边，
    // 用minRight维护当前基站可以建设的最远（右）位置
    int n = 1, minRight = arr[0].right;
    for (const auto& r : arr) {
        if (r.left > minRight) {
            n++;
            minRight = r.right;
        } else {
            minRight = min(minRight, r.right);
        }
    }

    return n;
}

int main() {
    vector<vector<int>> ranges = {{1, 4}, {2, 3}, {4, 5}};
    int n = minStations(ranges);
    cout << "基站数目: " << n << endl;
    return 0;
}